package org.shj.suanfa.sort

/**
 * 快速排序算法思想： 取一个数，通过一次排序把所有大于它的数放在其后，所有小于它的数放在其前面。然后对
 * 这个数的前后两部分，分别进行相同的操作。
 * 快速排序对大的数组比较有优势
 */
object QuickSort {
  def main(args: Array[String]): Unit = {
    val arr = Array(57, 68, 59, 42, 78, 28, 96, 33, 24, 19)
    quickSort(arr, 0, arr.length-1)
        
    arr.foreach(i => print(i + " "))
  }
  
  def quickSort(arr: Array[Int], low: Int, high: Int){
    var pivot = 0
    if(low < high){
      pivot = getPivot(arr, low, high)
      quickSort(arr, low, pivot - 1)
      quickSort(arr, pivot + 1, high)
    }    
  }
  
  //得到基准数的位置
  def getPivot(arr: Array[Int], from: Int, end: Int) : Int = {
    
    var low = from
    var high = end
    
    val pivotKey = arr(from)
    
    while(low < high){
      while(low < high && arr(high) >= pivotKey){
        high -= 1
      }
      arr(low) = arr(high)
      while(low < high && arr(low) <= pivotKey){
        low += 1
      }
      arr(high) = arr(low)
    }
    arr(low) = pivotKey
    low
  }
  
  def swap(arr:Array[Int], x:Int, y:Int){
    var tmp = arr(x)
    arr(x) = arr(y)
    arr(y) = tmp
  }
}